package com.husd.leetcode.math;

/**
 * 面试题 17.06. 2出现的次数
 *
 * 编写一个方法，计算从 0 到 n (含 n) 中数字 2 出现的次数。
 *
 * 示例:
 *
 * 输入: 25
 * 输出: 9
 * 解释: (2, 12, 20, 21, 22, 23, 24, 25)(注意 22 应该算作两次)
 * 提示：
 *
 * n <= 10^9
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/number-of-2s-in-range-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author hushengdong
 */
public class NumberOf2sInRange {

    //数位DP，字面意思就是在数位上进行dp。这种DP只和数组结构有关与数的大小没什么关系。
    //一般的题目是给你两个数，让你求这两个数之间符合条件的数的个数，且这两个数非常大，这样的题目一般就是数位DP 题。

    //找规律题 看起来可以动态规划来做，实际上n的值会非常大，不适合用动态规划

    // 10 : 2
    // 20 : 2 + 1
    //
    //n=10,2出现的次数为1,
    //n=100,2出现的次数为20 （[20:30]十位为2十次，[2,12,22,32,42,52,62,72,82,92]个位为2十次）
    //n=200,2出现的次数为(20x2)+1 （[200]百位为2一次，[0:199]十位为2二十次个位为2二十次，）
    //n=300,2出现的次数为(20x3)+100 ([200:300]百位为2一百次，[0:299]十位为2三十次个位为2三十次)
    //n=1000,2出现的次数为(20x10)+100（[200:300]百位为2一百次，[0:999]十位为2一百次个位为2一百次）
    //n=3000,2出现的次数为(300x3)+1000 ([2000:3000]千位为2一千次，一次1000中2出现的次数为300次）
    //
    //TODO 值得一看
    public int numberOf2sInRange(int n) {

        return 0;
    }
}
